package com.cqs.leetcode.tree;

public class Solution421 {


    //最高位权重
    final static int MAX_WIGHT = 1 << 30;

    public int findMaximumXOR(int[] nums) {
        Node root = buildTree(nums);
        int result = 0;
        for (int num : nums) {
            Node cur = root;
            int tmp = 0;
            for (int i = 0; i <= 30; i++) {
                //从高向地求某位的二进制的值
                int b = Math.min(1, num & (MAX_WIGHT >> i));
                //cur.children[1-b] != null 在i位可以异或得到1
                tmp += cur.children[1 - b] != null ? MAX_WIGHT >> i : 0;
                //一定是有值得， 优先选择异或值那一路
                cur = cur.children[1 - b] != null ? cur.children[1 - b] : cur.children[b];
            }
            result = Math.max(result, tmp);
        }
        return result;
    }

    private Node buildTree(int[] nums) {
        Node root = new Node();
        for (int num : nums) {
            Node cur = root;
            for (int i = 0; i <= 30; i++) {
                //从高位到地位。 注意num & (MAX_WIGHT >> i)得到的数据是2的幂等数
                int b = Math.min(num & (MAX_WIGHT >> i), 1);
                //这里一定是为空的时候才新建节点。否则了能会丢失i位之后的情况。
                if (cur.children[b] == null) {
                    cur.children[b] = new Node();
                }
                cur = cur.children[b];
            }
        }
        return root;
    }


    class Node {
        Node[] children = new Node[2];
    }
}
